
/**
 * 
 * 5G网络建设
 * 
 * 题目描述

现需要在某城市进行5G网络建设，已经选取N个地点设置5G基站，编号固定为1到N，接下来需要各个基站之间使用光纤进行连接以确保基站能互联互通，不同基站之间假设光纤的成本各不相同，且有些节点之间已经存在光纤相连。

请你设计算法，计算出能联通这些基站的最小成本是多少。

注意：基站的联通具有传递性，比如基站A与基站B架设了光纤，基站B与基站C也架设了光纤，则基站A与基站C视为可以互相联通。

输入描述
第一行输入表示基站的个数N，其中：

0 < N ≤ 20
第二行输入表示具备光纤直连条件的基站对的数目M，其中：

0 < M < N * (N - 1) / 2
从第三行开始连续输入M行数据，格式为

X Y Z P
其中：

X，Y 表示基站的编号

0 < X ≤ N
0 < Y ≤ N
X ≠ Y
Z 表示在 X、Y之间架设光纤的成本

0 < Z < 100
P 表示是否已存在光纤连接，0 表示未连接，1表示已连接

输出描述
如果给定条件，可以建设成功互联互通的5G网络，则输出最小的建设成本

如果给定条件，无法建设成功互联互通的5G网络，则输出 -1

用例
输入	3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出	4
说明	只需要在1，2以及1，3基站之间铺设光纤，其成本为3+1=4
输入	3
1
1 2 5 0
输出	-1
说明	3基站无法与其他基站连接，输出-1
输入	3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出	1
说明	2，3基站已有光纤相连，只要在1，3基站之间铺设光纤，其成本为1

 */

import java.util.Arrays;
import java.util.Scanner;

/**
  * 
  题目解析
（下图中，虚线代表节点之间可以铺设光纤，但是还没有铺设，实线表示已经铺好了）

用例1图示



用例2图示



用例3图示



本题是经典的最小生成树问题

生成树概念
而在了解最小生成树概念前，我们需要先了解生成树的概念：

在无向连通图中，生成树是指包含了全部顶点的极小连通子图。
生成树包含原图全部的n个顶点和n-1条边。（注意，边的数量一定是n-1）
比如下面无向连通图例子：



根据生成树概念，我们可以基于上面无向连通图，产生多个生成树，下面举几个生成树例子：



 

如上图我们用n-1条橙色边连接了n个顶点。这样就从无向连通图中产生了生成树。

为什么生成树只能由n-1条边呢？
因为少一条边，则生成树就无法包含所有顶点。多一条边，则生成树就会形成环。
而生成树最重要的两个特性就是：
1、包含所有顶点
2、无环
最小生成树概念
了解了生成树概念后，我们就可以进一步学习最小生成树了。

我们回头看看无向连通图，可以发现每条边都有权重值，比如v1-v2权重值是6，v3-v6权重值是4。

最小生成树指的是，生成树中n-1条边的权重值之和最小。

那么如何才能准确的找出一个无向连通图的最小生成树呢？

有两种算法：Prim算法和Kruskal算法。

Prim算法是基于顶点找最小生成树。Kruskal是基于边找最小生成树。

Prim算法
首先，我们介绍Prim算法：

我们可以选择无向连通图中的任意一个顶点作为起始点，比如我们选v1顶点为起始点



从v1顶点出发，有三条边，我们选择权重最小的1，即将v1-v3相连

 

此时我们需要将v1-v3看成一个整体，然后继续找这个整体出发的所有边里面的最小的， 



 可以发现为最小权重为4，因此，将v3-v6相连



接着将v1-v3-v6看出一个整体，找这个整体出发的所有边里面的最小的，可以找到最小权重2，因此将v6-v4相连



但是接下来，我们会发现，从v1-v3-v6-v4整体出发的所有边里面同时有三个最小权重5，那么该如何选择呢？



其实不难看出，如果选择v4-v3，或者v4-v1相连，则对应的生成树就形成了环结构，因此就不符合生成树特性了，因此我们只能选择v3-v2。

（注意：如果有多个相同的最小权重边可选，并且都不会产生环结构，则可以选择其中任意一条边，最终得到结果都是最小生成树） 
 其实，不仅仅在上面遇到相同权重边时，需要判断是否形成环，在前选择每一条边时都需要判断是否形成环，一旦选择的边能够形成环，那么我们就应该舍弃它，选择第二小的权重边，并继续判断。



按照上面逻辑，我们可以继续找到v1-v2-v3-v4-v6整体出发所有边中的最小权重边3，即将v2-v5相连，并且连接后不会形成环

 

此时选择的边数已经达到了n-1条，因此可以结束逻辑，而现在得到的就是最小生成树。我们可以将这个最小生成数的所有边的权重值之和计算出来为15。 

上面这种基于顶点的找最小生成树的方式就是Prim算法。

关于Prim算法具体实现细节请看代码实现，已添加详细注释。

Kruskal算法
接下来介绍Kruskal算法：

Kruskal算法要求我们将所有的边按照权重值升序排序，因此可得：



首先，我们将权重最小的边v1-v3加入，得到下图

 

接着将下个最小权重2的边v4-v6加入 



接着继续加最小权重边





 

此时边数已经达到n-1，而刚好这个过程中也没有环的形成，因此得到的就是最小生成树。

但是这里有巧合因素在里面，因为最后一步中，最小权重5的边有多条，如果并不是v2-v3排在前面呢，比如是v1-v4呢？



可以发现，形成了环，因此我们应该舍弃这条边，继续找剩下的最小权重边。最后总能找到v2-v3。

那么判断环的存在就是实现上面Prim算法和Kruskal算法的关键点！

其实，生成树就是一个连通分量，初始时，生成树这个连通分量只有一个顶点（Prim），或者两个顶点（Kruskal），后面会不断合入新的顶点进来，来扩大连通分量范围。

而连通分量可以使用并查集表示，

并查集本质就是一个长度为n的数组（n为无向图的顶点数），数组索引值代表图中某个顶点child，数组索引指向的元素值，代表child顶点的祖先顶点father。

初始时，每个child的father都是自己。即初始时，默认有n个连通分量。
比如 arr = [1,1,1,5,5,5] 数组就可以模拟出一个无向图



0顶点（索引值）的祖先是1顶点（元素值）  
1顶点（索引值）的祖先是1顶点（元素值） 
2顶点（索引值）的祖先是1顶点（元素值） 
我们可以用father指代一个连通分量。比如上面arr = [1,1,1,5,5,5]就有两个连通分量，分别是father为1的连通分量和father为5的连通分量。

最小生成树中的顶点必然都处于同一个连通分量中，因此每加入一个新的顶点child_new，我们我们就可以看它的father是否已经是连通分量对应的father，如果是，则说明顶点child_new其实已经存在于最小生成树中了，因此就产生了环，比如下面例子：

​

上面右图绿色部分（对应连通图中橙色实线），则arr变为

​

上面右图黄色部分（对应连通图中黑色实线），即v4顶点的father改成v1，但是实际上v4的father已经是v1，那么此时如果再强行加入的话，那么就形成了环。

Prim算法和Kruskal算法的适用场景
Prim算法是基于节点操作的，因此Prim算法适用于节点少，边多的情况

Kruskal算法是基于边操作的，因此Kruskal算法适用于节点多，边少的情况。

本题解析
本题属于最小生成树的变种题，区别于板子题，本题中主要是存在一些已经关联好的节点。

比如下面连通图中，2-3是已经连通好的。



其实处理起来也很简单，对于已经关联了的节点，我们可以认为他们之间的边权为0。

即上图中，2-3虽然边权为5，但是由于已经关联好了，因此可以认为实际边权为0。

这样的话，本题就变成最小生成树的板子题了。

  */
public class G5网络建设 {
    
    // 边
    static class Edge {
        int from; // 边起点
        int to; // 边终点
        int weight; // 边权重
    
        public Edge(int from, int to, int weight) {
        this.from = from;
        this.to = to;
        this.weight = weight;
        }
    }
 
    public static void main(String[] args) {

            Scanner sc = new Scanner(System.in);
        
            int n = sc.nextInt(); // 基站数量（节点数）
            int m = sc.nextInt(); // 基站对数量（边数）
        
            Edge[] edges = new Edge[m];
        
            for (int i = 0; i < m; i++) {
                int x = sc.nextInt();
                int y = sc.nextInt();
                int z = sc.nextInt();
                int p = sc.nextInt();
            
                // 如果p==1，则可以认为x-y边权为0
                edges[i] = new Edge(x, y, p == 0 ? z : 0);
            }
        
            System.out.println(kruskal(edges, n));
        }
    
        public static int kruskal(Edge[] edges, int n) {
            int minWeight = 0;
        
            // 按照边权升序
            Arrays.sort(edges, (a, b) -> a.weight - b.weight);
        
            UnionFindSet ufs = new UnionFindSet(n + 1);
        
            // 最先遍历出来是边权最小的边
            for (Edge edge : edges) {
                // 如果edge.from节点 和 edge.to节点 是同一个连通分量（即都在最小生成树中），则此时会产生环
                // 因此只有当edge.from节点 和 edge.to节点不在同一个连通分量时，才能合并（纳入最小生成树）
                if (ufs.find(edge.from) != ufs.find(edge.to)) {
                    minWeight += edge.weight;
                    ufs.union(edge.from, edge.to);
            
                    // 需要注意的是，上面初始化并查集的节点数为n+1个，因此并查集底层fa数组的长度就是n+1，即索引范围是[0, n]，左闭右闭，
                    // 其中0索引是无用的，1~n索引对应最小生成树中各个节点，如果者n个节点可以变为最小生成树，那么1~n节点会被合并为一个连通分量
                    // 而0索引虽然无用，但是也会自己形成一个连通分量，因此最终如果能形成最小生成树，则并查集中会有两个连通分量
                    if (ufs.count == 2) {
                        return minWeight;
                    }
                }
            }
        
            return -1;
        }

        private static // 并查集
        class UnionFindSet {
            public int[] fa;
            public int count;
            
            public UnionFindSet(int n) {
                this.fa = new int[n];
                this.count = n;
                for (int i = 0; i < n; i++) this.fa[i] = i;
            }
            
            public int find(int x) {
                if (x != this.fa[x]) {
                return (this.fa[x] = this.find(this.fa[x]));
                }
                return x;
            }
            
            public void union(int x, int y) {
                int x_fa = this.find(x);
                int y_fa = this.find(y);
            
                if (x_fa != y_fa) {
                this.fa[y_fa] = x_fa;
                this.count--;
                }
        }
    
    }
    }
